import java.util.LinkedList;
import java.util.Queue;

public class
_5Main {
    static int n = 30, m = 50;
    static char[][] maze;// 迷宫
    static int[][] dis;// 用于存储走出迷宫的路线
    static int[][] dir = { { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 0 } };// 下 左 右 上
    static char[] c = { 'D', 'L', 'R', 'U' };

    public static void main(String[] args) {
        String s = "01010101001011001001010110010110100100001000101010"
                + "00001000100000101010010000100000001001100110100101"
                + "01111011010010001000001101001011100011000000010000"
                + "01000000001010100011010000101000001010101011001011"
                + "00011111000000101000010010100010100000101100000000"
                + "11001000110101000010101100011010011010101011110111"
                + "00011011010101001001001010000001000101001110000000"
                + "10100000101000100110101010111110011000010000111010"
                + "00111000001010100001100010000001000101001100001001"
                + "11000110100001110010001001010101010101010001101000"
                + "00010000100100000101001010101110100010101010000101"
                + "11100100101001001000010000010101010100100100010100"
                + "00000010000000101011001111010001100000101010100011"
                + "10101010011100001000011000010110011110110100001000"
                + "10101010100001101010100101000010100000111011101001"
                + "10000000101100010000101100101101001011100000000100"
                + "10101001000000010100100001000100000100011110101001"
                + "00101001010101101001010100011010101101110000110101"
                + "11001010000100001100000010100101000001000111000010"
                + "00001000110000110101101000000100101001001000011101"
                + "10100101000101000000001110110010110101101010100001"
                + "00101000010000110101010000100010001001000100010101"
                + "10100001000110010001000010101001010101011111010010"
                + "00000100101000000110010100101001000001000000000010"
                + "11010000001001110111001001000011101001011011101000"
                + "00000110100010001000100000001000011101000000110011"
                + "10101000101000100010001111100010101001010000001000"
                + "10000010100101001010110000000100101010001011101000"
                + "00111100001000010000000110111000000001000000001011"
                + "10000001100111010111010001000110111010101101111000";
        Queue<Integer> queue = new LinkedList<Integer>();
        dis = new int[30][50];
        maze = new char[30][50];
        //1、将迷宫存储在一个二维数组maze中
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                maze[i][j] = s.charAt(0);
                s = s.substring(1, s.length());
            }

        }

        //2、目的是从迷宫终点往回走，算式(n - 1) * m + m - 1,这样利用运算符"\"和"%"即可获得迷宫终点
        queue.add((n - 1) * m + m - 1);

        //3、开始从迷宫终点由四个方向走迷宫,若所走的点在地图内且该点没有走过，将该点加入到queue中
        while (!queue.isEmpty()) {// queue不为空
            int temp = queue.poll();
            for (int i = 0; i < 4; i++) {// 四个方向
                int xx = temp / m + dir[i][0];
                int yy = temp % m + dir[i][1];
                if (xx < 0 || xx >= n || yy < 0 || yy >= m || maze[xx][yy] == '1' || dis[xx][yy] != 0)
                    continue;
                queue.add(xx * m + yy);
                //3.1 设置当前点所走的下一个点的值等于当前点加1
                dis[xx][yy] = dis[temp / m][temp % m] + 1;
                //3.2 若迷宫从终点走到起点，则停止走迷宫
                if (xx == 0 && yy == 0)
                    break;
            }
        }

        //4、设置迷宫终点改为没有走过的点，目的是我们需要描述迷宫走的路径
        dis[n - 1][m - 1] = 0;

        String record = "";

        //5、从起点开始用字符串描述走迷宫的路径，从四个方向走迷宫
        //若下一个点在迷宫内并且该点不是障碍物(障碍物为1)且该点的值等于当前点减1，即是我们第3步所走的路径，则字符串加上该方向
        int x = 0, y = 0;
        while (x != n - 1 || y != m - 1) {//迷宫未走到终点
            for (int i = 0; i < 4; i++) {//从四个方向走迷宫
                int xx = x + dir[i][0];
                int yy = y + dir[i][1];
                if (xx < 0 || xx >= n || yy < 0 | yy >= m || maze[xx][yy] == '1')
                    continue;
                if (dis[x][y] == dis[xx][yy] + 1) {
                    x = xx;
                    y = yy;
                    record += c[i];
                    break;
                }
            }
        }
        System.out.println(record);
    }
}

